11269. Lemurian parties – easy
Lemur King Julian has exactly 2 ⋅ k lemurs under his control, 2 lemurs of each
of k species. Julian loves to party, so he throws a party every night,
but the VIP area unfortunately only has enough seats for him and n other
lemurs.
Since Julian doesn’t like having “the same”
parties, he has to choose every day who to invite to
the VIP area so that the sets of lemurs from the VIP area never repeat. Two
lemurs of the same species are considered indistinguishable. Sets are considered
equal if they match as multisets of lemur species.
Help Julian determine how many days he can
hold various parties. Since the answer can be large, print it modulo 109
+ 7.
Input. One line contains two integers k and n (1 ≤ k ≤ 500
000, 0 ≤ n ≤ 2 * k) – the number of lemur species and the number of seats
in the VIP area.
Output. Print one number – the answer to the problem modulo 109
+ 7.
|
Sample
input 1 |
Sample output 1 |
|
3 3 |
7 |
|
|
|
|
Sample
input 2 |
Sample output 2 |
|
4 3 |
16 |
SOLUTION
combinatorics
Algorithm analysis
For n
places, some species will be represented by two lemurs, and some by one. Let i
pairs of lemurs be chosen (i species are represented by two lemurs),
this choice can be made in 
ways. After
that, n – 2i seats will
remain in the VIP zone. This number of lemurs can be chosen from the k – i remaining
species (one lemur from each of the k – i remaining
species). This choice can be made in 
number of ways. Since i
can take any value from 0 to k, we get the answer
Example
Consider the
second test
case, where there are k = 4 pairs of lemurs and n = 3 places in
the VIP zone. According to the formula we get:
= 
+ 
= 4 + 12 = 16
Let’s write
out only nonzero terms. 
is considered equal to zero if one of the
three inequalities is satisfied: k < 0, n < 0 or k > n.
Denote the
lemurs with the letters {a, a, b,
b, c, c, d, d}. The same letters correspond to
lemurs of the same type. The term = 4 corresponds to the
fact that no two lemurs of
the same species are chosen, each of the three chosen lemurs belongs to
different species. The possible 4 options are:
Consider the term = 12. Two lemurs were selected from one species (4
variants). For the remaining one place, one lemur is selected from the three
remaining species. There are 12 options:
Obviously, it is
impossible to take two lemurs from two species for 3 places. Therefore, the
remaining terms of the sum are equal to zero.
Algorithm realization
Declare the constants.
#define MAX 1000001
#define MOD 1000000007
Declare the arrays: fact
contains the factorials of numbers modulo MOD, factinv contains the inverces of the
factorials of numbers modulo MOD:
fact[n] = n!
mod 1000000007
factinv[n] = n!
-1 mod 1000000007
typedef long long ll;
ll fact[MAX], factinv[MAX];
The function pow computes the power of a number modulo: xn mod p.
ll pow(ll x, ll n, ll p)
{
if (n == 0) return 1;
if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
return (x * pow(x, n - 1, p)) % p;
}
The function inverse finds the inverse of x
modulo p. Since the number p is prime, then by Fermat’s theorem xp-1 mod p = 1 for every 1 ≤ x < p. The equality
can be rewritten in the form (x * xp-2) mod p = 1, whence the inverse of x is xp-2 mod p.
ll inverse(ll x, ll p)
{
return pow(x, p - 2, p);
}
The function Cnk computes the binomial
coefficient using the formula:
=
ll Cnk(int n, int k)
{
return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}
The main part of the program. Read the input data.
scanf("%d %d", &k, &n);
Fill the arrays of factorials fact and factinv.
fact[0] =
1;
for (i = 1; i < MAX; i++)
fact[i] = (fact[i - 1] * i) % MOD;
factinv[0]
= 1;
for (i = 1; i < MAX; i++)
factinv[i] = inverse(fact[i], MOD);
Compute the answer using the formula 
. The value of the binomial coefficient we consider
equal to zero if one of the three inequalities is satisfied: k < 0, n < 0 or
k > n.
res = 0;
for (i = 0; i <= k; i++)
{
if (n - 2 * i < 0 || k -
i < 0 || n - 2 * i > k - i) continue;
res = (res + Cnk(k, i) * Cnk(k - i, n - 2 *
i)) % MOD;
}
Print the answer.
printf("%lld\n", res);